You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.
The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer's value set to its depth.
Return the sum of each integer in nestedList multiplied by its depth.
Example 1:
Input: nestedList = [[1,1],2,[1,1]] Output: 10 Explanation: Four 1's at depth 2, one 2 at depth 1. 1*2 + 1*2 + 2*1 + 1*2 + 1*2 = 10.
Example 2:
Input: nestedList = [1,[4,[6]]] Output: 27 Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.
Example 3:
Input: nestedList = [0] Output: 0
Constraints:
1 <= nestedList.length <= 50- The values of the integers in the nested list is in the range
[-100, 100]. - The maximum depth of any integer is less than or equal to
50.
Average Rating: 4.86 (71 votes)
Video Solution
Solution Article
Approach 1: Depth-first Search
Because the input is nested, it is natural to think about the problem in a recursive way. We go through the list of nested integers one by one, keeping track of the current depth d. If a nested integer is an integer, n, we calculate its sum as n×d. If the nested integer is a list, we calculate the sum of this list recursively using the same process but with depth equals d+1.
Implementation
Complexity Analysis
Let N be the total number of nested elements in the input list. For example, the list [ [[[[1]]]], 2 ] contains 4 nested lists and 2 nested integers (1 and 2), so N=6 for that particular case.
-
Time complexity : O(N).
Recursive functions can be a bit tricky to analyze, particularly when their implementation includes a loop. A good strategy is to start by determining how many times the recursive function is called, and then how many times the loop will iterate across all calls to the recursive function.
The recursive function,
dfs(...)is called exactly once for each nested list. As N also includes nested integers, we know that the number of recursive calls has to be less than N.On each nested list, it iterates over all of the nested elements directly inside that list (in other words, not nested further). As each nested element can only be directly inside one list, we know that there must only be one loop iteration for each nested element. This is a total of N loop iterations.
So combined, we are performing at most 2⋅N recursive calls and loop iterations. We drop the 2 as it is a constant, leaving us with time complexity O(N).
-
Space complexity : O(N).
In terms of space, at most O(D) recursive calls are placed on the stack, where D is the maximum level of nesting in the input. For example, D=2 for the input
[[1,1],2,[1,1]], and D=3 for the input[1,[4,[6]]].In the worst case, D=N, (e.g. the list
[[[[[[]]]]]]) so the worst-case space complexity is O(N).
Approach 2: Breadth-first Search
We can also solve the problem using a breadth-first search. The algorithm for this is closely based on the standard breadth-first search template. The algorithm fully processes each depth before moving to the next one.
Implementation
Complexity Analysis
-
Time complexity : O(N).
Similar to the DFS approach. Each nested element is put on the queue and removed from the queue exactly once.
-
Space complexity : O(N).
The worst-case for space complexity in BFS occurs where most of the elements are in a single layer, for example, a flat list such as
[1, 2, 3, 4, 5]as all of the elements must be put on the queue at the same time. Therefore, this approach also has a worst-case space complexity of O(N).
May 19, 2020 5:41 AM
BFS:
class Solution {
public int depthSum(List<NestedInteger> nestedList) {
Queue<NestedInteger> q = new LinkedList<>();
for(NestedInteger n : nestedList){
q.add(n);
}
int deep = 1;
int ans = 0;
while(!q.isEmpty()){
int size = q.size();
for(int i = 0; i < size; i++){
NestedInteger temp = q.poll();
if(temp.isInteger()){
ans += deep * temp.getInteger();
}else{
for(NestedInteger n : temp.getList()){
q.add(n);
}
}
}
deep++;
}
return ans;
}
}
DFS:
class Solution {
public int depthSum(List<NestedInteger> nestedList) {
return dfs(nestedList, 1);
}
public int dfs(List<NestedInteger> nestedList, int deep){
int ans = 0;
for(NestedInteger n : nestedList){
if(n.isInteger()) ans += (deep * n.getInteger());
else ans += dfs(n.getList(), deep + 1);
}
return ans;
}
}
August 3, 2020 7:35 PM
Python recursive solution
class Solution(object):
def depthSum(self, nestedList):
"""
:type nestedList: List[NestedInteger]
:rtype: int
"""
return self.recSum(nestedList, 1)
def recSum(self, nestedList, depth):
sum = 0
for item in nestedList:
if item.isInteger():
sum += (item.getInteger() * depth)
else:
sum += self.recSum(item.getList(), depth+1)
return sum
May 12, 2020 6:17 AM
Python DFS
class Solution:
def depthSum(self, nestedList: List[NestedInteger]) -> int:
if not nestedList: return 0
total = 0
stack = [(l, 1) for l in nestedList]
while stack:
l, index = stack.pop()
value = l.getInteger()
if value is not None:
total += value * index
else:
for item in l.getList():
stack.append((item, index + 1))
return total
Last Edit: September 5, 2018 9:11 AM
My non recursive solution:
public class Solution {
public int depthSum(List nestedList) {
int ans = 0, depth = 1;
Queue<List> queue = new LinkedList<>();
queue.offer(nestedList);
queue.offer(null);
while(!queue.isEmpty()){
List t = queue.poll();
if(t == null){
depth ++;
if(!queue.isEmpty())
queue.offer(null);
continue;
}
for(NestedInteger n : t){
if(n.isInteger()){
ans = ans + depth * n.getInteger();
}else{
queue.offer(n.getList());
}
}
}
return ans;
}
}
March 13, 2020 3:34 PM
My iterative solution:
stack = [[1, nestedList]]
count = 0
while len(stack):
weight, nest = stack.pop()
for i in nest:
if i.isInteger():
count += i.getInteger() * weight
else:
stack.append([weight + 1, i.getList()])
return count
January 9, 2020 3:28 PM
class Solution(object):
def depthSum(self, nestedList):
"""
:type nestedList: List[NestedInteger]
:rtype: int
"""
def lfunc(nestedList, l, res):
for x in nestedList:
if x.isInteger():
n = x.getInteger()
res += n * l
else:
res += lfunc(x.getList(), l + 1, 0)
return res
return lfunc(nestedList, 1, 0)
October 29, 2019 1:34 PM
iterative... even slow
cpp:
class Solution {
public:
int depthSum(vector<NestedInteger>& nestedList) {
int res = 0;
int level = 1;
while (!nestedList.empty()) {
vector<NestedInteger> nextLevel;
for (auto n : nestedList) {
if (n.isInteger())
res += n.getInteger() * level;
else
nextLevel.insert(nextLevel.end(), n.getList().begin(), n.getList().end());
}
nestedList = nextLevel;
level++;
}
return res;
}
};
Java:
class Solution {
public int depthSum(List<NestedInteger> nestedList) {
int res = 0;
int level = 1;
while (!nestedList.isEmpty()) {
List<NestedInteger> nextLevelList = new LinkedList<>();
for (NestedInteger nestedInteger : nestedList) {
if (nestedInteger.isInteger()) {
res += nestedInteger.getInteger() * level;
} else {
nextLevelList.addAll(nextLevelList.size(), nestedInteger.getList());
}
}
nestedList = nextLevelList;
level++;
}
return res;
}
}
July 10, 2019 11:06 PM
Can't we use BFS in this problem? Since technically this is a level order traversal?
May 13, 2018 3:51 AM
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
* // Constructor initializes an empty nested list.
* public NestedInteger();
*
* // Constructor initializes a single integer.
* public NestedInteger(int value);
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // Set this NestedInteger to hold a single integer.
* public void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* public void add(NestedInteger ni);
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return null if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
class Solution {
int sum = 0;
public int depthSum(List<NestedInteger> nestedList) {
maxDepth(nestedList,1);
return sum;
}
public void maxDepth(List<NestedInteger> ni,int i){
for (NestedInteger n : ni){
if (n.isInteger()){
sum=sum+n.getInteger()*i;
}else {
maxDepth(n.getList(),i+1);
}
}
}
}
January 30, 2019 8:59 AM
Can anyone explain why do we do the method overload here?
xxxxxxxxxx/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * class NestedInteger { * public: * // Constructor initializes an empty nested list. * NestedInteger(); * * // Constructor initializes a single integer. * NestedInteger(int value); * * // Return true if this NestedInteger holds a single integer, rather than a nested list. * bool isInteger() const; * * // Return the single integer that this NestedInteger holds, if it holds a single integer * // The result is undefined if this NestedInteger holds a nested list * int getInteger() const; * * // Set this NestedInteger to hold a single integer. * void setInteger(int value); * * // Set this NestedInteger to hold a nested list and adds a nested integer to it. * void add(const NestedInteger &ni); * * // Return the nested list that this NestedInteger holds, if it holds a nested list * // The result is undefined if this NestedInteger holds a single integer * const vector<NestedInteger> &getList() const; * }; */// DFS Approachclass Solution {public: int depthSum(vector<NestedInteger>& nestedList) { return dfs(nestedList, 1); } int dfs(vector<NestedInteger>& list, int depth) { int res = 0; for(NestedInteger nested : list) {